Algorithme de Floyd-Warshall
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
En informatique, l'algorithme de Floyd-Warshall est un algorithme pour déterminer les distances des plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré, en temps cubique au nombre de sommets. Il est parfois appelé algorithme de Roy-Floyd-Warshall car il a été décrit par Bernard Roy en 1959cite-ref-1[1] avant la parution des articles de Floyd et Warshall datant de 1962.
Contents
• Exemple
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Algorithme
L'algorithme de Floyd-Warshall prend en entrée un graphe orienté et valué, décrit par une matrice d'adjacence donnant le poids d'un arc lorsqu'il existe et la valeur ∞ sinon. Le poids d'un chemin entre deux sommets est la somme des poids sur les arcs constituant ce chemin. Les arcs du graphe peuvent avoir des poids négatifs, mais le graphe ne doit pas posséder de circuit de poids strictement négatif. L'algorithme calcule, pour chaque paire de sommets, le poids minimal parmi tous les chemins entre ces deux sommets.
L'algorithme de Floyd-Warshall est un exemple de programmation dynamique. Soit G = ( S , A ) {\displaystyle G=(S,A)} un graphe à n {\displaystyle n} sommets avec S = { s 1 , s 2 , … … , s n } {\displaystyle S=\{s_{1},s_{2},\dots ,s_{n}\}} . Il résout successivement les sous-problèmes suivants :
W i j k {\displaystyle {\mathcal {W}}_{ij}^{k}} est le poids minimal d'un chemin du sommet s i ∈ ∈ S {\displaystyle s_{i}\in S} au sommet s j ∈ ∈ S {\displaystyle s_{j}\in S} n'empruntant que des sommets intermédiaires dans { s 1 , s 2 , … … , s k } ∈ ∈ S {\displaystyle \{s_{1},s_{2},\dots ,s_{k}\}\in S} s'il en existe un, et ∞ ∞ {\displaystyle \infty } sinon.
On note W k {\displaystyle {\mathcal {W}}^{k}} la matrice des W i j k {\displaystyle {\mathcal {W}}_{ij}^{k}} . Pour k = 0 {\displaystyle k=0} , W 0 {\displaystyle {\mathcal {W}}^{0}} est la matrice d'adjacence définissant G {\displaystyle G} . Maintenant, pour trouver une relation de récurrence, on considère un chemin p {\displaystyle p} entre s i {\displaystyle s_{i}} et s j {\displaystyle s_{j}} de poids minimal dont les sommets intermédiaires sont dans { s 1 , s 2 , … … , s k } {\displaystyle \{s_{1},s_{2},\dots ,s_{k}\}} . De deux choses l'une :
• soit p {\displaystyle p} n'emprunte pas le sommet s k {\displaystyle s_{k}} ;
• soit p {\displaystyle p} emprunte exactement une fois le sommet s k {\displaystyle s_{k}} (car les circuits sont de poids positifs ou nuls) et p {\displaystyle p} est donc la concaténation de deux chemins, entre s i {\displaystyle s_{i}} et s k {\displaystyle s_{k}} et s k {\displaystyle s_{k}} et s j {\displaystyle s_{j}} respectivement, dont les sommets intermédiaires sont dans { s 1 , s 2 , … … , s k − − 1 } {\displaystyle \{s_{1},s_{2},\dots ,s_{k-1}\}} .
L'observation ci-dessus donne la relation de récurrence W i j k = min ( W i j k − − 1 , W i k k − − 1 + W k j k − − 1 ) {\displaystyle {\mathcal {W}}_{ij}^{k}=\min({\mathcal {W}}_{ij}^{k-1},{\mathcal {W}}_{ik}^{k-1}+{\mathcal {W}}_{kj}^{k-1})} , pour tous i {\displaystyle i} , j {\displaystyle j} et k {\displaystyle k} dans { 1 , 2 , … … , n } {\displaystyle \{1,2,\dots ,n\}} . Ainsi on résout les sous-problèmes par valeur de k {\displaystyle k} croissante.
Pseudo-code
Donnons d'abord une première version d'après l'analyse faite dans la section précédente. Le pseudo-code suivant effectue ce calcul :
fonction FloydWarshall (
G
{\displaystyle G}
)
W
0
:=
{\displaystyle {\mathcal {W}}^{0}:=}
matrice d'adjacence de
G
{\displaystyle G}
(matrice
n
×
n
{\displaystyle {\mathit {n}}\times {\mathit {n}}}
)
for
k
:=
1
{\displaystyle {\mathit {k}}:=1}
to
n
{\displaystyle {\mathit {n}}}
for
i
:=
1
{\displaystyle {\mathit {i}}:=1}
to
n
{\displaystyle {\mathit {n}}}
for
j
:=
1
{\displaystyle {\mathit {j}}:=1}
to
n
{\displaystyle {\mathit {n}}}
W
i
j
k
=
min
(
W
i
j
k
−
1
,
W
i
k
k
−
1
+
W
k
j
k
−
1
)
{\displaystyle {\mathcal {W}}_{ij}^{k}=\min({\mathcal {W}}_{ij}^{k-1},{\mathcal {W}}_{ik}^{k-1}+{\mathcal {W}}_{kj}^{k-1})}
renvoyer
W
n
{\displaystyle {\mathcal {W}}^{n}}
On peut optimiser l'algorithme en effectuant le calcul en place dans une unique matrice W {\displaystyle {\mathcal {W}}} . Le pseudo-code suivant effectue ce calcul :
fonction FloydWarshall (
G
{\displaystyle G}
)
W
:=
{\displaystyle {\mathcal {W}}:=}
matrice d'adjacence de
G
{\displaystyle G}
(matrice
n
×
n
{\displaystyle {\mathit {n}}\times {\mathit {n}}}
)
for
k
:=
1
{\displaystyle {\mathit {k}}:=1}
to
n
{\displaystyle {\mathit {n}}}
for
i
:=
1
{\displaystyle {\mathit {i}}:=1}
to
n
{\displaystyle {\mathit {n}}}
for
j
:=
1
{\displaystyle {\mathit {j}}:=1}
to
n
{\displaystyle {\mathit {n}}}
W
i
j
:=
min
(
W
i
j
,
W
i
k
+
W
k
j
)
{\displaystyle {\mathcal {W}}_{{\mathit {i}}{\mathit {j}}}:=\min({\mathcal {W}}_{{\mathit {i}}{\mathit {j}}},{\mathcal {W}}_{{\mathit {i}}{\mathit {k}}}+{\mathcal {W}}_{{\mathit {k}}{\mathit {j}}})}
renvoyer
W
{\displaystyle {\mathcal {W}}}
La complexité en temps, dans le pire cas, de cet algorithme (deuxième version) est O ( n 3 ) {\displaystyle O(n^{3})} et sa complexité en espace O ( n 2 ) {\displaystyle O(n^{2})} .
Exemple
L'algorithme est exécuté sur le graphe à gauche.
• Pour k = 0 {\displaystyle k=0} , les seuls chemins sont les arcs directs.
• Pour k = 1 {\displaystyle k=1} , on regarde les chemins où le sommet s 1 {\displaystyle s_{1}} peut être un sommet intermédiaire. On trouve le chemin s 2 → → s 1 → → s 3 {\displaystyle s_{2}\rightarrow s_{1}\rightarrow s_{3}} qui est moins lourd que s 2 → → s 3 {\displaystyle s_{2}\rightarrow s_{3}} .
• Pour k = 2 {\displaystyle k=2} , maintenant, le sommet s 2 {\displaystyle s_{2}} peut être un sommet intermédiaire. La boîte rouge et la boîte bleu montrent que le chemin s 4 → → s 2 → → s 1 → → s 3 {\displaystyle s_{4}\rightarrow s_{2}\rightarrow s_{1}\rightarrow s_{3}} est la concaténation du chemin s 4 → → s 2 {\displaystyle s_{4}\rightarrow s_{2}} et s 2 → → s 1 → → s 3 {\displaystyle s_{2}\rightarrow s_{1}\rightarrow s_{3}} avec le sommet s 2 {\displaystyle s_{2}} comme sommet intermédiaire. Notons que le chemin s 4 → → s 2 → → s 3 {\displaystyle s_{4}\rightarrow s_{2}\rightarrow s_{3}} n'est pas considéré car c'est s 2 → → s 1 → → s 3 {\displaystyle s_{2}\rightarrow s_{1}\rightarrow s_{3}} qui est un chemin le plus léger obtenu à l'itération précédente et non s 2 → → s 3 {\displaystyle s_{2}\rightarrow s_{3}} .
• Pour k = 3 {\displaystyle k=3} , on trouve encore d'autres chemins.
• Pour k = 4 {\displaystyle k=4} , on a trouvé des plus courts chemins entre tous les sommets.
Applications
L'algorithme de Floyd-Warshall peut être utilisé dans les situations suivantes :
• Plus courts chemins dans les graphes orientés non pondérés (en donnant un poids 1 à chaque arc)
• Clôture transitive d'un graphe orienté (algorithme de Warshall). Dans la formulation initiale de l'algorithme ci-dessus par Warshall, le graphe n'est pas valué et donc simplement représenté par une matrice de booléens. On obtient alors la clôture transitive de ce graphe en remplaçant dans l'algorithme ci-dessus l'addition par la conjonction (ET) et le minimum par la disjonction (OU).
• Trouver une expression régulière dénotant le langage rationnel défini par un automate fini. Les formules sont celles connues sous le nom d’algorithme de McNaughton et Yamada.
Améliorations
En 1993, Bahar et coll. ont donné une implémentation de l'algorithme de Floyd-Warshall pour des graphes représentés symboliquement à l'aide d'une structure de données appelée diagramme de décision algébriques qui est une généralisation des diagrammes de décision binairecite-ref-2[2].
Notes et références
cite-note-11. ↑ roy1959bernard-roy1959Bernard Roy, « Transitivité et connexité. », C. R. Acad. Sci. Paris, vol. 249, 1959, p. 216–218
cite-note-22. ↑ baharfrohmgaonahachtel1993r-iris-baharerica-a-frohmcharles-m-gaonagary-d-hachtel1993R. Iris Bahar, Erica A. Frohm, Charles M. Gaona et Gary D. Hachtel, « Algebraic decision diagrams and their applications », ICCAD '93 Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, IEEE Computer Society Press, 7 novembre 1993, p. 188–191 (ISBN 0818644907, lire en ligne, consulté le 9 février 2018)
Références
• cormenleisersonriveststein2001thomas-h-cormencharles-e-leisersonronald-l-rivestclifford-stein2001(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2e éd. [détail de l’édition]
• Section 26.2, "The Floyd-Warshall algorithm", p. 558–565;
• Section 26.4, "A general framework for solving path problems in directed graphs", p. 570–576.
• floyd1962robert-w-floyd1962(en) Robert W. Floyd, « Algorithm 97: Shortest Path », Communications of the ACM, vol. 5, no 6, juin 1962, p. 345 (DOI 10.1145/367766.368168)
• warshall1962stephen-warshall1962(en) Stephen Warshall, « A theorem on Boolean matrices », Journal of the ACM, vol. 9, no 1, janvier 1962, p. 11–12 (DOI 10.1145/321105.321107)
Voir aussi
• Portail de l'informatique théorique